The present invention relates to encoding data for transmission through a channel and for decoding such encoded data after its transmission through a channel. In particular, the present invention relates to encoders and decoders in communication systems for information storage and retrieval.
Information that is transmitted from a source to a destination can be considered generically to pass through a channel. In some communication systems, the channel comprises electromagnetic radiation passing through the atmosphere. In other communication systems, the channel comprises a long conductor between the source and destination. Still other communication systems comprise a magnetic disk, where information from the source is stored on the disk and later retrieved from the disk for delivery to the destination.
In early storage systems, an analog read signal was generated from the disk and converted into digital data by assuming that a current digital value was unaffected by its predecessor values in the read signal. Later systems recognized that the writing and reading operations could be modeled as a communication channel and that this communication channel exhibited certain partial response characteristics in which neighboring values in the channel affected each other.
Using this channel model, many current systems utilize a Partial Response Maximum Likelihood (PRML) approach when attempting to detect and decode data read from a storage medium. Under PRML, a read signal is generated from the medium and sampled to produce a sequence of samples. These samples are then passed through a filter to fit the samples to a desired channel response. A detector then determines the most likely data sequence given the sequence of samples.
Before storing the data on the medium, most systems encode the data to improve certain performance characteristics. In particular, most codes attempt to limit the number of consecutive same symbols in the data. This is especially important in storage systems that detect physical transitions along the medium in order to read back data. In such systems, a binary xe2x80x9c1xe2x80x9d is typically written as a transition on the medium and a binary xe2x80x9c0xe2x80x9d is typically written as no transition. If there are too many consecutive 1""s in the data, the transitions on the medium can interfere with each other. If there are too many consecutive 0""s, the system is not able to generate an accurate read clock from the data.
Recently, some codes have been devised that limit the number of consecutive 1""s to less than four. In such codes, it has been found that detection errors can occur when three consecutive 1""s in a code word are mistakenly detected as beginning one code bit earlier or one code bit later than where they actually begin. This type of error has come to be known as a shifted tribit error.
To reduce the likelihood of a shifted tribit error, codes have been developed that limit the starting positions of tribits in the code word. (See W. Bliss, xe2x80x9cAn 8/9 rate time-varying trellis code for high density recording,xe2x80x9d Intermag 97; and P. Siegel et al.,xe2x80x9d An 8/9 rate trellis code for E2PR4,xe2x80x9d presented UCSD CMRR, May 1997.) Under these codes, tribits are allowed to begin at either even code bit positions or odd code bit positions but not both. In a detector for such a code, detection paths that include tribits beginning outside of an allowed bit position are removed from consideration. Thus, a shifted tribit error cannot occur because a recovered word with a shifted tribit is not recognized as a valid code word.
Although such codes reduce tribit errors, they also reduce the number of available code words that can be used during encoding. In some cases, the reduction means that a particular code rate cannot be achieved because there are not enough code words. For example, a rate 9/10 code (9 data bits converted into 10 code bits), that prevents tribit shifting as discussed above would not have enough code words to support each of the possible data words. In other cases, the reduction in code words requires that code words with undesirably long sequences of consecutive 0""s must be used. Thus, a code is needed that reasonably protects against tribit shift errors while providing more code words than current techniques.
An encoder is provided that converts data words into code words. The code words, when concatenated together, are such that sub-strings of consecutive first symbols in the code words have no more symbols than a maximum number; sub-strings having the maximum number of consecutive first symbols and beginning at selected locations within the code words appear without restriction, and sub-strings having the maximum number of consecutive first symbols and beginning at locations other than the selected locations appear only where the substring is concatenated with an acceptable secondary sub-string.
A method is also provided for generating a set of code words for an encoder. The method includes eliminating code words that have strings of consecutive first symbols that are longer than a maximum length and retaining some code words that have a string of consecutive first symbols that is as long as the maximum length if the string begins at a selected location. The method further includes retaining some code words that have a string of consecutive first symbols that is as long as the maximum length and that begins at a location other than a selected location if the string is concatenated with an acceptable sub-string. If the string of consecutive symbols is not concatenated with an acceptable sub-string, the code word is eliminated.